package com.leetcode.partition8;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/10/11 18:16
 */
public class LC743网络延迟时间 {

    private static final int MAX = Integer.MAX_VALUE >> 1;

    public static int networkDelayTime(int[][] times, int n, int k) {
        return dijkstra(times, n, k);
    }

    public static void main(String[] args) {
        int[][] times = {{2, 1, 1}, {2, 3, 1}, {3, 4, 1}};
        int n = 4, k = 2;
        System.out.println(networkDelayTime(times, n, k));
    }

    private static int dijkstra(int[][] times, int n, int k) {
        int answer = -1;
        int[][] matrix = new int[n + 1][n + 1];
        boolean[] visited = new boolean[n + 1];
        for (int[] matrixTime : matrix) Arrays.fill(matrixTime, MAX);
        //根据边构建领接矩阵
        for (int[] time : times) {
            matrix[time[0]][time[1]] = time[2];
        }
        //从k结点开始
        visited[k] = true;
        matrix[k][k] = 0;
        for (int count = 0; count < matrix.length - 1; count++) {
            int nearestIndex = -1, nearestDistance = MAX;
            //找出从k节点开始最近的未访问过的邻节点
            for (int j = 1; j < matrix[0].length; j++) {
                if (!visited[j] && matrix[k][j] < nearestDistance) {
                    nearestIndex = j;
                    nearestDistance = matrix[k][j];
                }
            }
            //找不到最近节点，直接返回
            if (nearestIndex == -1) break;
            matrix[k][nearestIndex] = nearestDistance;
            visited[nearestIndex] = true;
            //以nearestIndex为中心更新k到其它点的最小距离
            for (int i = 1; i < matrix.length; i++) {
                int dis = matrix[k][nearestIndex] + matrix[nearestIndex][i];
                if (!visited[i] && matrix[k][i] > dis) {
                    matrix[k][i] = dis;
                }
            }
        }
        Arrays.stream(matrix).forEach(val -> System.out.println(Arrays.toString(val)));

        for (int i = 1; i < matrix[0].length; i++) {
            if (i == k) continue;
            if (matrix[k][i] == MAX) return -1;
            answer = Math.max(answer, matrix[k][i]);
        }
        System.out.println(Arrays.toString(matrix[k]));
        return answer;
    }
}
